// var mergeKLists = function (lists) {
//     // 分治，递归调用自己拆成一个个链表
//     if (lists.length === 0) return;
//     if (lists.length === 1) return lists[0];
//     let mid = Math.floor(lists.length / 2)
//     let left = mergeKLists(lists.slice(0, mid))
//     let right = mergeKLists(lists.slice(mid))
//     return merge(left, right);
// };

// function merge(left, right) {
//     let dummy = new ListNode(0)
//     let cur = dummy
//     while (left && right) {
//         if (left.val < right.val) {
//             cur.next = left
//             left = left.next
//         } else {
//             cur.next = right
//             right = right.next
//         }
//         cur = cur.next
//     }
//     cur.next = left || right
//     return dummy.next
// }

var mergeKLists = function (lists) {
    if (lists.length === 0) return;
    if (lists.length === 1) return lists[0];
    let mid = Math.floor(lists.length / 2);
    let left = mergeKLists(lists.slice(0, mid));
    let right = mergeKLists(lists.slice(mid));
    return merge(left, right)
}

function merge(left, right) {
    let dummy = new ListNode();
    let cur = dummy;

    while (left && right) {
        if (left.val < right.val) {
            cur.next = left;
            left = left.next;
        } else {
            cur.next = right;
            right = right.next;
        }
        cur = cur.next;
    }
    cur.next = left || right;
    return dummy.next;
}